package com.c2b.algorithm.leetcode.hot100;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 * <a href="https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/">无重复字符的最长子串</a>
 * <p>给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。</p>
 * <pre>
 * 示例 1:
 *
 *      输入: s = "abcabcbb"
 *      输出: 3
 *      解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 *
 * 示例 2:
 *      输入: s = "bbbbb"
 *      输出: 1
 *      解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 *
 * 示例 3:
 *      输入: s = "pwwkew"
 *      输出: 3
 *      解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
 *          请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 * </pre>
 * <b>提示：</b>
 * <li>0 <= s.length <= 5 * 10^4</li>
 * <li>s 由英文字母、数字、符号和空格组成</li>
 *
 * @author c2b
 * @since 2023/4/18 16:37
 */
public class Hot003LengthOfLongestSubstring_M {

    /**
     * 基于队列的滑动窗口
     */
    public int lengthOfLongestSubstring(String s) {
        int maxLength = 0;
        if (s == null || s.length() == 0) {
            return maxLength;
        }
        Queue<Character> queue = new LinkedList<>();
        for (int i = 0; i < s.length(); ++i) {
            if (queue.contains(s.charAt(i))) {
                while (!queue.isEmpty()) {
                    if (queue.poll() == s.charAt(i)) {
                        break;
                    }
                }
            }
            queue.offer(s.charAt(i));
            maxLength = Math.max(maxLength, queue.size());
        }
        return maxLength;
    }

    /**
     * 基于队列的滑动窗口
     */
    public int lengthOfLongestSubstring2(String s) {
        int ans = 0;
        if (s == null || s.length() == 0) {
            return ans;
        }
        // 用map记录上一次字符出现的位置
        Map<Character, Integer> map = new HashMap<>();
        int start = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (map.containsKey(s.charAt(i))) {
                // 进入到这里说明该字符已经出现过。重新统计
                start = Math.max(start, map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i), i);
            ans = Math.max(ans, i - start + 1);
        }
        return ans;
    }


    public static void main(String[] args) {
        System.out.println(new Hot003LengthOfLongestSubstring_M().lengthOfLongestSubstring2("pwwkew"));
    }
}
